// C Includes
#include <sys/time.h>
#include <stdio.h>
#include <stdlib.h>

// C++ Includes
#include <STLVector.hpp>
#include <STLString.hpp>

// Local Includes
#include <BPlusTree.hpp>


template <typename TN>class MemoryNodeStorage:
  public FTSS::NodeStorage<TN>
{
public:
	// Create node storage
	FTSS::Result_t CreateStorage(FTSS::KeySize_t iMaxNodesCount) throw();
	// Set current root node ID
	void SetRootNodeId(const FTSS::BTreeNodeID_t & iNodeID)  throw();
	// Get current root node ID
	FTSS::BTreeNodeID_t GetRootNodeId() const throw();
	// Create a new B-Tree node and lock it
	TN * CreateAndLock(FTSS::BTreeNodeID_t & iNodeID) throw();
	// Get and lock existing node
	TN * GetAndLock(const FTSS::BTreeNodeID_t & iNodeID,  FTSS::LockMode_t iLockMode) throw();
	// Unlock node
	int Unlock(const FTSS::BTreeNodeID_t & iNodeID) throw();
	// Destroy Node
	int Destroy(const FTSS::BTreeNodeID_t & iNodeID) throw();
	// Synchonize node to the hard disk
	int Sync(const FTSS::BTreeNodeID_t & iNodeID) throw();
	// Constructor
	MemoryNodeStorage();
	// Destructor
	~MemoryNodeStorage() throw();
	// Debug level
	void Debug(const FTSS::Level_t & iLevel) throw();
	int iScore;
private:
	// Root Node ID
	FTSS::BTreeNodeID_t oRootNodeId;
	// Statistics
	int iLevel;

	int iDAScore;
	// DataStorage
	STLW::vector<TN *> vStorage;

public:

void Score() throw()
{
	fprintf(stderr, "Lock/Unlock Score: %d\n",   iScore);
	fprintf(stderr, "Alloc/Dealloc Score: %d\n", iDAScore);
}

};

//
// Constructor
//
template <typename TN> MemoryNodeStorage<TN>::MemoryNodeStorage(): iScore(0), oRootNodeId(0), iLevel(0), iDAScore(0) { ;; }

//
// Create node storage
//
template <typename TN>
  FTSS::Result_t MemoryNodeStorage<TN>::CreateStorage(FTSS::KeySize_t iMaxNodesCount) throw() { return 0; }

//
// Set current root node ID
//
template <typename TN>
  void MemoryNodeStorage<TN>::SetRootNodeId(const FTSS::BTreeNodeID_t & iNodeID) throw() { oRootNodeId = iNodeID; }

//
// Get current root node ID
//
template <typename TN>
  FTSS::BTreeNodeID_t MemoryNodeStorage<TN>::GetRootNodeId() const throw() { return oRootNodeId; }

//
// Create a new B-Tree node and lock it
//
template <typename TN>
  TN * MemoryNodeStorage<TN>::CreateAndLock(FTSS::BTreeNodeID_t & iNodeID) throw()
{
	iScore++;
	iDAScore++;

	TN * pNode = new TN;
	vStorage.push_back(pNode);
	iNodeID = vStorage.size();
if (iLevel) { fprintf(stderr, "CreateAndLock: %p - %d\n", pNode, iNodeID); }
return pNode;
}

//
// Get and lock existing node
//
template <typename TN>
  TN * MemoryNodeStorage<TN>::GetAndLock(const FTSS::BTreeNodeID_t & iNodeID, FTSS::LockMode_t iLockMode) throw()
{
	iScore++;
if (iLevel) { fprintf(stderr, "GetAndLock: %p - %d\n", vStorage[iNodeID - 1], iNodeID); }
	return vStorage[iNodeID - 1];
}

//
// Unlock node
//
template <typename TN>
  int MemoryNodeStorage<TN>::Unlock(const FTSS::BTreeNodeID_t & iNodeID) throw()
{
	iScore--;
if (iLevel) { fprintf(stderr, "Unlock: %d\n",  iNodeID); }
	return 0;
}

//
// Destroy Node
//
template <typename TN>
  int MemoryNodeStorage<TN>::Destroy(const FTSS::BTreeNodeID_t & iNodeID) throw()
{
if (iLevel) { fprintf(stderr, "Destroy: %d\n",  iNodeID); }
	delete vStorage[iNodeID - 1];
	iDAScore--; iScore--;
	return 0;
}

//
// Synchonize node to the hard disk
//
template <typename TN>
  int MemoryNodeStorage<TN>::Sync(const FTSS::BTreeNodeID_t & iNodeID) throw()
{
//fprintf(stderr, "Sync: %d\n",  iNodeID);
	return 0;
}

//
// Destructor
//
template <typename TN>
  MemoryNodeStorage<TN>::~MemoryNodeStorage() throw()
{
	fprintf(stderr, "Lock/Unlock Score: %d\n",   iScore);
	fprintf(stderr, "Alloc/Dealloc Score: %d\n", iDAScore);
}

// Debug level
template <typename TN>
  void MemoryNodeStorage<TN>::Debug(const FTSS::Level_t & iILevel) throw() { iLevel = iILevel; }



// ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
template<typename T, FTSS::KeySize_t TreeWidth>class MemoryNode:
public MemoryNodeStorage<FTSS::BPlusNode<T, TreeWidth> >
{
public:
	~MemoryNode() throw() { ;; }
};

template<typename T, typename V, FTSS::KeySize_t TreeWidth>class MemoryLeaf:
public MemoryNodeStorage<FTSS::BPlusLeaf<T, V, TreeWidth> >
{
public:
	~MemoryLeaf() throw() { ;; }
};


template <typename T, typename V, FTSS::KeySize_t TreeWidth>void print(FTSS::BPlusNodeType * pType, bool recurse, STLW::string indent)
{
	STLW::string sbuf;
	STLW::string next_indent = indent + "  ";
	if (pType -> is_leaf)
	{
		FTSS::BPlusLeaf<T, V, TreeWidth> * pLeaf = (FTSS::BPlusLeaf<T, V, TreeWidth> *)(pType);
		fprintf(stdout, "%s", indent.c_str());
		// print values
		for (int i = 0; i < pLeaf -> size; ++i)
		{
			fprintf(stdout, "|%d => %d", pLeaf -> pairs[i].first, pLeaf -> pairs[i].second);
		}
		for (int i = pLeaf -> size; i < TreeWidth; ++i)
		{
			fprintf(stdout, "|-       ");
		}
		fprintf(stdout, "|   L:%d\n", pLeaf -> size);
	}
	else
	{
		FTSS::BPlusNode<T, TreeWidth> * pNode = (FTSS::BPlusNode<T, TreeWidth> *)(pType);

		fprintf(stdout, "%s", indent.c_str());
		// print separators
		for (int i = 0; i < pNode -> size; ++i)
		{
			fprintf(stdout, "|%d", pNode -> keys[i]);
		}
		for (int i = pNode -> size; i < TreeWidth; ++i)
		{
			fprintf(stdout, "%s|-",indent.c_str());
		}
		fprintf(stdout, "|   I:%d\n", pNode -> size);

		if (recurse)
		{
			// if needed, recurse for each child
			for (int i = 0; i <= pNode -> size; ++i)
			{
				print<T, V, TreeWidth>(pNode -> children[i], recurse, next_indent);
			}
		}
	}
}

template <typename T, typename V, FTSS::KeySize_t TreeWidth>void printTree(FTSS::BPlusNodeType * pType)
{
	print<T, V, TreeWidth>(pType, true, "");
	fprintf(stdout, "\n");
}


int main(void)
{
	MemoryNode<int, 10> oNodeStorage;
	MemoryLeaf<int, int, 10> oLeafStorage;

	FTSS::BPlusTree<int, int, 10> oTree(&oNodeStorage, &oLeafStorage);
	//FTSS::BPlusTree<int, int, 10> oTree(NULL, NULL);

	STLW::vector<int> vElements;

	srandom(time(NULL));
	printf("=== Fill tree =====================================\n");
	int * aElements = new int [15000];
	int iPrev  = 0;
	int iPrevT = 0;

	fprintf(stdout, "Duplicate keys: ");

	for (int i = 0; i < 15000; i++)
	{
		aElements[i] = iPrev + (random() & 0x7F);
		iPrev = aElements[i];

		if (iPrevT == iPrev) { fprintf(stdout, "%d ", iPrevT); }

		iPrevT = iPrev;
	}


	printf("\n");
	for (int i = 0; i < 15000; i++)
	{
//		if (i != 0 && i % 50 == 0) { fprintf(stdout, "\n"); }
		FTSS::Pair<int, int> oPair;
		oPair.first = aElements[i];
		oPair.second = i + 100;
		oTree.Insert(oPair);
		//fprintf(stdout, "%c", oTree.Insert(oPair) ? '.':'!');
	}

//printTree<int, int, 10>(oTree.root);
	printf("\n=== Remove elements from tree =====================\n");
	for (int i = 0; i < 15000; i++)
	{
		if (i != 0 && i % 50 == 0) { fprintf(stdout, "\n"); }
		if (oTree.Remove(aElements[i]) == 0)
		{
			fprintf(stdout, "!");
			vElements.push_back(aElements[i]);
		}
		else { fprintf(stdout, "."); }
	}
//printTree<int, int, 10>(oTree.root);
	fprintf(stdout, "\nDuplicate keys: ");

	delete [] aElements;
}
// End.
